package org.hot100_3;

import java.nio.charset.MalformedInputException;
import java.util.List;

public class leetcode148 {
    public ListNode sortList(ListNode head) {

        if (head==null){
            return head;
        }

        return split(head, null);
    }

    private ListNode split(ListNode head, ListNode tail) {

        if (head.next == tail) {
            //确保链表断开
            head.next=null;
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast != tail) {
            fast = fast.next;
            slow = slow.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }

        ListNode mid = slow;

        ListNode left = split(head, mid);
        ListNode right = split(mid, tail);

        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {

        ListNode dummy = new ListNode(-1);

        ListNode node = dummy;

        while (left != null && right != null) {
            if (left.val < right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }
            node = node.next;
        }

        if (left == null) {
            node.next = right;
        }

        if (right == null) {
            node.next = left;
        }

        return dummy.next;
    }
}
